#include <bits/stdc++.h>

using namespace std;

// 数字2的个数
// 给定一个整数n
// 计算所有小于等于n的非负整数中数字2出现的个数
// 测试链接 : https://leetcode.cn/problems/number-of-2s-in-range-lcci/

class Solution 
{
public:
    int numberOf2sInRange(int n) 
    {
        return cnt(n, 2);
    }

    int cnt(int num, int d)
    {
        int ans = 0;
        for(long right = 1, tmp = num, left, cur; tmp != 0; right *= 10, tmp /= 10)
        {
            left = tmp / 10;
            cur = tmp % 10;
            if(d == 0) --left;
            ans += left * right;
            if(cur > d) ans += right;
            else if(cur == d) ans += num % right + 1;
        }
        return ans;
    }
};


class Solution 
{
public:
    int numberOf2sInRange(int n) 
    {
        auto s = to_string(n);
        int m = s.size(), dp[m][m];
        memset(dp, -1, sizeof(dp));
        function<int(int, int, bool)> f = [&](int i, int cnt, bool is_limit)
        {
            if(i == m) return cnt;
            if(!is_limit && dp[i][cnt] != -1) return dp[i][cnt];
            
            int up = is_limit ? s[i] - '0' : 9;
            int ret = 0;
            for(int d = 0; d <= up; ++d)
            {
                ret += f(i + 1, cnt + (d == 2), is_limit && d == up);
            }
            if(!is_limit) dp[i][cnt] = ret;
            return ret;
        };
        
        return f(0, 0, true);
    }
};